package com.zp.self.module.level_4_算法练习.算法.位图;

import java.util.HashMap;
import java.util.Map;

/**
 * @author By ZengPeng
 */
public class 力扣_567_字符串的排列 {
    //测试
    public static void main(String[] args) {

        System.out.println(new 力扣_567_字符串的排列().checkInclusion("ab","dbaooo"));
        System.out.println(new 力扣_567_字符串的排列().checkInclusion("ab","eidboaoo"));
        System.out.println(new 力扣_567_字符串的排列().checkInclusion("abc","bbbca"));
    }

    /**
    题目：给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。
          如果是，返回 true ；否则，返回 false 。
          换句话说，s1 的排列之一是 s2 的 子串 。

     示例 1：
     输入：s1 = "ab" s2 = "eidbaooo"
     输出：true
     解释：s2 包含 s1 的排列之一 ("ba").

     示例 2：
     输入：s1= "ab" s2 = "eidboaoo"
     输出：false

    分析：【P 💓💗💖💘💝】
       1.左右指针 + hash: 每段记录值
         --执行用时：28 ms, 在所有 Java 提交中击败了17.64%的用户
       2.左右指针 + 位图：记录位图中字符串两个字符串每个字符的差数
                          差距数=0时，count++，26个都为0时，证明全部都有了，返回true
         --执行用时：5 ms, 在所有 Java 提交中击败了77.81%的用户
    边界值 & 注意点：
       1.
     **/
    public boolean checkInclusion(String s1, String s2) {
        int len1 = s1.length(),len2 = s2.length();
        if(len1>len2)return false;
        int left=0,right=len1-1,count=0;
        int[] arr = new int[26];
        for (int i = 0; i < len1; i++) {
            arr[s1.charAt(i)-'a']++;
            arr[s2.charAt(i)-'a']--;
        }
        for (int anArr : arr) {
            if (anArr == 0) count++;
        }
        if(count==26)return true;
        int lv,rv;
        while (++right<len2){
            lv = s2.charAt(left)-'a';
            rv =  s2.charAt(right)-'a';
            if(++arr[lv] == 1)
                count--;
            else if(arr[lv] == 0)
                count++;

            if(--arr[rv] == 0){
                if(++count==26)return true;
            }else if(arr[rv] == -1)
                count--;
            left++;
        }
        return false;

        //1.左右指针 + hash
        /*Map<Character,Integer> map1= new HashMap<>();
        Map<Character,Integer> map2= new HashMap<>();
        for (int i = 0; i < len1; i++) {
            map1.put(s1.charAt(i),map1.getOrDefault(s1.charAt(i),0)+1);
            map2.put(s2.charAt(i),map2.getOrDefault(s2.charAt(i),0)+1);
        }
        if(isEquals(map1, map2))return true;

        while (++right<len2){
            //判断两个map的内容是否相等
            map2.put(s2.charAt(right),map2.getOrDefault(s2.charAt(right),0)+1);
            char charAtLeft = s2.charAt(left);
            if(map2.get(charAtLeft)==1)
                map2.remove(charAtLeft);
            else
                map2.put(charAtLeft,map2.get(charAtLeft)-1);
            left++;
            if(isEquals(map1, map2))return true;
        }
        return false;*/
    }

    private boolean isEquals(Map<Character, Integer> map1, Map<Character, Integer> map2) {
        if(map1.size()!=map2.size())
            return false;
        for (Character char1 : map1.keySet()) {
            if(!map1.get(char1).equals(map2.get(char1)))
                return false;
        }
        return true;
    }
}
